package shuju;

class BinaryTree {
    private class TreeNode {
        int data;
        TreeNode left, right;

        TreeNode(int data) {
            this.data = data;
            left = right = null;
        }
    }

    private TreeNode root;

    public BinaryTree() {
        root = null;
    }

    // 添加节点
    public void add(int value) {
        root = addRec(root, value);
    }

    private TreeNode addRec(TreeNode node, int value) {
        if (node == null) {
            node = new TreeNode(value);
            return node;
        }
        if (value < node.data) {
            node.left = addRec(node.left, value);
        } else if (value > node.data) {
            node.right = addRec(node.right, value);
        }
        return node;
    }

    // 中序遍历
    public void inorder() {
        inorderRec(root);
        System.out.println();
    }

    private void inorderRec(TreeNode node) {
        if (node != null) {
            inorderRec(node.left);
            System.out.print(node.data + " ");
            inorderRec(node.right);
        }
    }

    // 查找节点
    public boolean contains(int value) {
        return containsRec(root, value);
    }

    private boolean containsRec(TreeNode node, int value) {
        if (node == null) {
            return false;
        }
        if (value == node.data) {
            return true;
        }
        return value < node.data ? containsRec(node.left, value) : containsRec(node.right, value);
    }

    // 获取树的高度
    public int height() {
        return heightRec(root);
    }

    private int heightRec(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftHeight = heightRec(node.left);
        int rightHeight = heightRec(node.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }
}
